package com.base.dp;

public class CountGoodStrings {
    public static void main(String[] args) {
        CountGoodStrings countGoodStrings = new CountGoodStrings();
        System.out.println(countGoodStrings.countGoodStrings(3, 3, 1, 1));
    }

    private static final int MOD = 1000000007;

    public int countGoodStrings(int low, int high, int zero, int one) {
        //我们可以定义一个 DP 数组 dp[i]，表示构造长度为 i 的字符串的方案数。由于我们需要构造的字符串长度在 low 和 high 之间，我们只需要计算这个范围内的方案数。
        //初始化：创建一个 DP 数组 dp，其大小为 high + 1，并将 dp[0] 初始化为 1，因为空字符串有一种构造方法。
        //状态转移：对于每个长度 i 从 1 到 high，我们需要考虑通过添加 zero 个 ‘0’ 或者 one 个 ‘1’ 来达到这个长度。因此，我们可以更新 dp[i] 如下：
        //如果 i 大于等于 zero，那么 dp[i] 可以通过在长度为 i - zero 的字符串后面添加 zero 个 ‘0’ 来构造，所以 dp[i] += dp[i - zero]。
        //如果 i 大于等于 one，那么 dp[i] 可以通过在长度为 i - one 的字符串后面添加 one 个 ‘1’ 来构造，所以 dp[i] += dp[i - one]。
        //由于答案可能很大，我们在每一步都取模 10^9 + 7。
        //最后，我们需要计算长度在 low 和 high 之间的所有字符串的方案数，可以通过计算 dp[low] 到 dp[high] 的和来实现。

        int[] dp = new int[high + 1];
        dp[0] = 1;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) {
                //为什么使用+=
                //累积效应：在动态规划中，dp[i] 代表的是到达长度 i 的所有可能构造方法的数量。如果我们仅仅使用 =，那么我们就只考虑了最后一种添加 zero 个 ‘0’ 的情况，而忽略了之前已经累积的其他构造方法。
                //多种添加方式：在每一步，我们都有可能通过添加 zero 个 ‘0’ 或者 one 个 ‘1’ 来构造长度为 i 的字符串。这意味着对于每一个 i，我们都需要加上所有可能的前一个状态（即 i - zero 和 i - one）的方案数。
                //状态转移：dp[i] 的值应该是由所有可以到达 i 的状态转移过来的。例如，如果我们已经计算出了 dp[i - zero] 和 dp[i - one]，那么 dp[i] 应该是这两者之和，因为它们都代表了到达 i 的不同路径。
                dp[i] += dp[i - zero];
            }
            if (i >= one) {
                dp[i] += dp[i - one];
            }
            dp[i] %= MOD;
        }
        long result = 0;
        for (int i = low; i <= high; i++) {
            result += dp[i];
            result %= MOD;
        }

        return (int) result;
    }

}
